package com.base.dynamicprograming;

/**
 * 639. 解码方法 II
 * 题目描述：https://leetcode-cn.com/problems/decode-ways-ii/
 *
 * @author leon
 * @date 2021年09月27日 20:32
 */
public class NumDecondings2 {

    /**
     * 题解结果不对，暂时没有找到原因
     */
    final int MOD = 1000000007;
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        // f(0)代表空字符串时，组合为1
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '*') {
                if (s.charAt(i - 1) != '0') {
                    f[i] += f[i - 1] % MOD;
                }
                if (i > 1 && s.charAt(i - 2) != '*') {
                    if (s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                        f[i] += f[i - 2] % MOD;
                    }
                } else if(i > 1 && s.charAt(i - 2) == '*'){
                    for (int j = 1; j < 3; j++) {
                        if (j * 10 + (s.charAt(i - 1) - '0') <= 26) {
                            f[i] += f[i - 2] % MOD;
                        }
                    }
                }

            } else {
                f[i] += 9 * f[i - 1] % MOD;
                // 代表 * 的 9个数
                for (int k = 1; k < 10; k++) {
                    if (i > 1 && s.charAt(i - 2) != '*') {
                        if (s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + k <= 26)) {
                            f[i] += f[i - 2] % MOD;
                        }
                    } else if(i > 1 && s.charAt(i - 2) == '*'){
                        for (int j = 1; j < 3; j++) {
                            if (j * 10 + k  <= 26) {
                                f[i] += f[i - 2] % MOD;
                            }
                        }
                    }
                }

            }
        }
        return f[n];
    }


    //    https://leetcode-cn.com/problems/decode-ways-ii/solution/gong-shui-san-xie-fen-qing-kuang-tao-lun-902h/
    final int mod = (int)1e7+9;
    public int numDecodings1(String s) {
        int n = s.length();
        long[] f = new long[3];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            char c = s.charAt(i - 1);
            int t = c - '0';
            long cnt = 0;
            int p1 = (i - 1) % 3, p2 = (i - 2) % 3;
            // 枚举组成什么 item（A -> 1; B -> 2 ...）
            for (int item = 1; item <= 26; item++) {
                if (item < 10) { // 该 item 由一个字符组成
                    if (c == '*' || t == item) cnt += f[p1];
                } else { // 该 item 由两个字符组成
                    if (i - 2 < 0) break;
                    char prev = s.charAt(i - 2);
                    int u = prev - '0';
                    int a = item / 10, b = item % 10;
                    if ((prev == '*' || u == a) && (t == b || (c == '*' && b != 0))) cnt += f[p2];
                }
            }
            f[i % 3] = cnt % mod;
        }
        return (int)(f[n % 3]);
    }
}